package com.wj.algorithm.lintcode;


public class P31 {
    
    public int partitionArray(int[] nums, int k) {
        if(nums == null) {
            return 0;
        }
        int len = nums.length;
        
        int headIndex = 0;
        int tailIndex = len - 1;
        while(headIndex <= tailIndex) {
            int head = nums[headIndex];
            int tail = nums[tailIndex];

            if(head >= k && tail < k) {
                //交换
                nums[headIndex] = tail;
                nums[tailIndex] = head;
                headIndex ++;
                tailIndex --;
            } else {
                if(head < k) {
                    headIndex ++;
                }
                if(tail >= k) {
                    tailIndex --;
                }
            }
        }

        int rs = nums.length;
        
        for(int i = 0; i < len; i ++) {
            if(nums[i] >= k) {
                return i;
            }
        }
        
        return rs;
    }

    public static void main(String[] args) {
        System.out.println(new P31().partitionArray(new int[] { 3, 2, 2, 1 }, 2));
    }
}
